Search Results

Documents authored by Saraf, Shubhangi

Document
DOI: 10.4230/LIPIcs.CCC.2023.15
Near-Optimal Set-Multilinear Formula Lower Bounds

Authors: Deepanshu Kush and Shubhangi Saraf

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for set-multilinear formulas. In this paper, we make progress along this direction by proving near-optimal lower bounds against low-depth as well as unbounded-depth set-multilinear formulas. More precisely, we show that over any field of characteristic zero, there is a polynomial f computed by a polynomial-sized set-multilinear branching program (i.e., f is in set-multilinear VBP) defined over Θ(n²) variables and of degree Θ(n), such that any product-depth Δ set-multilinear formula computing f has size at least n^Ω(n^{1/Δ}/Δ). Moreover, we show that any unbounded-depth set-multilinear formula computing f has size at least n^{Ω(log n)}. If such strong lower bounds are proven for the iterated matrix multiplication (IMM) polynomial or rather, any polynomial that is computed by an ordered set-multilinear branching program (i.e., a further restriction of set-multilinear VBP), then this would have dramatic consequences as it would imply super-polynomial lower bounds for general algebraic formulas (Raz, J. ACM 2013; Tavenas, Limaye, and Srinivasan, STOC 2022). Prior to our work, either only weaker lower bounds were known for the IMM polynomial (Tavenas, Limaye, and Srinivasan, STOC 2022), or similar strong lower bounds were known but for a hard polynomial not known to be even in set-multilinear VP (Kush and Saraf, CCC 2022; Raz, J. ACM 2009). By known depth-reduction results, our lower bounds are essentially tight for f and in general, for any hard polynomial that is in set-multilinear VBP or set-multilinear VP. Any asymptotic improvement in the lower bound (for a hard polynomial, say, in VNP) would imply super-polynomial lower bounds for general set-multilinear circuits.
Cite as

Deepanshu Kush and Shubhangi Saraf. Near-Optimal Set-Multilinear Formula Lower Bounds. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 15:1-15:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kush_et_al:LIPIcs.CCC.2023.15,
  author =	{Kush, Deepanshu and Saraf, Shubhangi},
  title =	{{Near-Optimal Set-Multilinear Formula Lower Bounds}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{15:1--15:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.15},
  URN =		{urn:nbn:de:0030-drops-182855},
  doi =		{10.4230/LIPIcs.CCC.2023.15},
  annote =	{Keywords: Algebraic Complexity, Set-multilinear, Formula Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.38
Improved Low-Depth Set-Multilinear Circuit Lower Bounds

Authors: Deepanshu Kush and Shubhangi Saraf

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
In this paper, we prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial f in VNP defined over n² variables, and of degree n, such that any product-depth Δ set-multilinear formula computing f has size at least n^Ω(n^{1/Δ}/Δ). The hard polynomial f comes from the class of Nisan-Wigderson (NW) design-based polynomials. Our lower bounds improve upon the recent work of Limaye, Srinivasan and Tavenas (STOC 2022), where a lower bound of the form (log n)^Ω(Δ n^{1/Δ}) was shown for the size of product-depth Δ set-multilinear formulas computing the iterated matrix multiplication (IMM) polynomial of the same degree and over the same number of variables as f. Moreover, our lower bounds are novel for any Δ ≥ 2. The precise quantitative expression in our lower bound is interesting also because the lower bounds we obtain are "sharp" in the sense that any asymptotic improvement would imply general set-multilinear circuit lower bounds via depth reduction results. In the setting of general set-multilinear formulas, a lower bound of the form n^Ω(log n) was already obtained by Raz (J. ACM 2009) for the more general model of multilinear formulas. The techniques of LST (which extend the techniques of the same authors in (FOCS 2021)) give a different route to set-multilinear formula lower bounds, and allow them to obtain a lower bound of the form (log n)^Ω(log n) for the size of general set-multilinear formulas computing the IMM polynomial. Our proof techniques are another variation on those of LST, and enable us to show an improved lower bound (matching that of Raz) of the form n^Ω(log n), albeit for the same polynomial f in VNP (the NW polynomial). As observed by LST, if the same n^Ω(log n) size lower bounds for unbounded-depth set-multilinear formulas could be obtained for the IMM polynomial, then using the self-reducibility of IMM and using hardness escalation results, this would imply super-polynomial lower bounds for general algebraic formulas.
Cite as

Deepanshu Kush and Shubhangi Saraf. Improved Low-Depth Set-Multilinear Circuit Lower Bounds. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kush_et_al:LIPIcs.CCC.2022.38,
  author =	{Kush, Deepanshu and Saraf, Shubhangi},
  title =	{{Improved Low-Depth Set-Multilinear Circuit Lower Bounds}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.38},
  URN =		{urn:nbn:de:0030-drops-166003},
  doi =		{10.4230/LIPIcs.CCC.2022.38},
  annote =	{Keywords: algebraic circuit complexity, complexity measure, set-multilinear formulas}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.CCC.2020
LIPIcs, Volume 169, CCC 2020, Complete Volume

Authors: Shubhangi Saraf

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
LIPIcs, Volume 169, CCC 2020, Complete Volume
Cite as

35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 1-1068, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{saraf:LIPIcs.CCC.2020,
  title =	{{LIPIcs, Volume 169, CCC 2020, Complete Volume}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{1--1068},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020},
  URN =		{urn:nbn:de:0030-drops-125518},
  doi =		{10.4230/LIPIcs.CCC.2020},
  annote =	{Keywords: LIPIcs, Volume 169, CCC 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.CCC.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Shubhangi Saraf

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{saraf:LIPIcs.CCC.2020.0,
  author =	{Saraf, Shubhangi},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.0},
  URN =		{urn:nbn:de:0030-drops-125520},
  doi =		{10.4230/LIPIcs.CCC.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.5
DEEP-FRI: Sampling Outside the Box Improves Soundness

Authors: Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space U is δ-far in relative Hamming distance from a linear code V - this is the worst-case assumption - then most elements of U are almost-δ-far from V - this is the average case. However, this result was known to hold only below the "double Johnson" function of the relative distance δ_V of the code V, i.e., only when δ < 1-(1-δ_V)^(1/4). First, we increase the soundness-bound to the "one-and-a-half Johnson" function of δ_V and show that the average distance of U from V is nearly δ for any worst-case distance δ smaller than 1-(1-δ_V)^(1/3). This bound is tight, which is somewhat surprising because the one-and-a-half Johnson function is unfamiliar in the literature on error correcting codes. To improve soundness further for Reed Solomon codes we sample outside the box. We suggest a new protocol in which the verifier samples a single point z outside the box D on which codewords are evaluated, and asks the prover for the value at z of the interpolating polynomial of a random element of U. Intuitively, the answer provided by the prover "forces" it to choose one codeword from a list of "pretenders" that are close to U. We call this technique Domain Extending for Eliminating Pretenders (DEEP). The DEEP method improves the soundness of the worst-case-to-average-case reduction for RS codes up their list decoding radius. This radius is bounded from below by the Johnson bound, implying average distance is approximately δ for all δ < 1-(1-δ_V)^(1/2). Under a plausible conjecture about the list decoding radius of Reed-Solomon codes, average distance from V is approximately δ for all δ. The DEEP technique can be generalized to all linear codes, giving improved reductions for capacity-achieving list-decodable codes. Finally, we use the DEEP technique to devise two new protocols: - An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. The soundness of the protocol improves upon that of the FRI protocol of [Ben-Sasson et al., ICALP 2018] while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity. - An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) protocol used to construct zero knowledge scalable transparent arguments of knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol, called DEEP-ALI, improves soundness of this crucial step from a small constant < 1/8 to a constant arbitrarily close to 1.
Cite as

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 5:1-5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bensasson_et_al:LIPIcs.ITCS.2020.5,
  author =	{Ben-Sasson, Eli and Goldberg, Lior and Kopparty, Swastik and Saraf, Shubhangi},
  title =	{{DEEP-FRI: Sampling Outside the Box Improves Soundness}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{5:1--5:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.5},
  URN =		{urn:nbn:de:0030-drops-116901},
  doi =		{10.4230/LIPIcs.ITCS.2020.5},
  annote =	{Keywords: Interactive Oracle Proofs of Proximity, STARK, Low Degree Testing}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.68
On List Recovery of High-Rate Tensor Codes

Authors: Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, and Shashwat Silas

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is approximately locally list recoverable, as well as globally list recoverable in probabilistic near-linear time. This was used in turn to give the first capacity-achieving list decodable codes with (1) local list decoding algorithms, and with (2) probabilistic near-linear time global list decoding algorithms. This also yielded constant-rate codes approaching the Gilbert-Varshamov bound with probabilistic near-linear time global unique decoding algorithms. In the current work we obtain the following results: 1) The tensor product of an efficient (poly-time) high-rate globally list recoverable code is globally list recoverable in deterministic near-linear time. This yields in turn the first capacity-achieving list decodable codes with deterministic near-linear time global list decoding algorithms. It also gives constant-rate codes approaching the Gilbert-Varshamov bound with deterministic near-linear time global unique decoding algorithms. 2) If the base code is additionally locally correctable, then the tensor product is (genuinely) locally list recoverable. This yields in turn (non-explicit) constant-rate codes approaching the Gilbert-Varshamov bound that are locally correctable with query complexity and running time N^{o(1)}. This improves over prior work by Gopi et. al. (SODA'17; IEEE Transactions on Information Theory'18) that only gave query complexity N^{epsilon} with rate that is exponentially small in 1/epsilon. 3) A nearly-tight combinatorial lower bound on output list size for list recovering high-rate tensor codes. This bound implies in turn a nearly-tight lower bound of N^{Omega(1/log log N)} on the product of query complexity and output list size for locally list recovering high-rate tensor codes.
Cite as

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, and Shashwat Silas. On List Recovery of High-Rate Tensor Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 68:1-68:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kopparty_et_al:LIPIcs.APPROX-RANDOM.2019.68,
  author =	{Kopparty, Swastik and Resch, Nicolas and Ron-Zewi, Noga and Saraf, Shubhangi and Silas, Shashwat},
  title =	{{On List Recovery of High-Rate Tensor Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{68:1--68:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.68},
  URN =		{urn:nbn:de:0030-drops-112832},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.68},
  annote =	{Keywords: Coding theory, Tensor codes, List-decoding and recovery, Local codes}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.24
Worst-Case to Average Case Reductions for the Distance to a Code

Authors: Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions vec{u}=(u_1,..., u_k), given as oracles, from a linear error correcting code V. The soundness of such systems relies on methods that act "locally" on vec{u} and map it to a single function u^* that is, roughly, as far from V as are u_1,..., u_k. Motivated by these applications to efficient proof systems, we study a natural worst-case to average-case reduction of distance for linear spaces, and show several general cases in which the following statement holds: If some member of a linear space U=span(u_1,...,u_k) is delta-far from (all elements) of V in relative Hamming distance, then nearly all elements of U are (1-epsilon)delta-far from V; the value of epsilon depends only on the distance of the code V and approaches 0 as that distance approaches 1. Our results improve on the previous state-of-the-art which showed that nearly all elements of U are 1/2delta-far from V [Rothblum, Vadhan and Wigderson, STOC 2013]. When V is a Reed-Solomon (RS) code, as is often the case for algebraic proof systems, we show how to boost distance via a new "local" transformation that may be useful elsewhere. Relying on the affine-invariance of V, we map a vector u to a random linear combination of affine transformations of u, and show this process amplifies distance from V. Assuming V is an RS code with sufficiently large distance, this amplification process converts a function u that is somewhat far from V to one that is (1-epsilon)-far from V; as above, epsilon depends only on the distance of V and approaches 0 as the distance of V approaches 1. We give two concrete application of these techniques. First, we revisit the axis-parallel low-degree test for bivariate polynomials of [Polischuk-Spielman, STOC 1994] and prove a "list-decoding" type result for it, when the degree of one axis is extremely small. This result is similar to the recent list-decoding-regime result of [Chiesa, Manohar and Shinkar, RANDOM 2017] but is proved using different techniques, and allows the degree in one axis to be arbitrarily large. Second, we improve the soundness analysis of the recent RS proximity testing protocol of [Ben-Sasson et al., ICALP 2018] and extend it to the "list-decoding" regime, bringing it closer to the Johnson bound.
Cite as

Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. Worst-Case to Average Case Reductions for the Distance to a Code. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bensasson_et_al:LIPIcs.CCC.2018.24,
  author =	{Ben-Sasson, Eli and Kopparty, Swastik and Saraf, Shubhangi},
  title =	{{Worst-Case to Average Case Reductions for the Distance to a Code}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.24},
  URN =		{urn:nbn:de:0030-drops-88654},
  doi =		{10.4230/LIPIcs.CCC.2018.24},
  annote =	{Keywords: Proximity testing, Reed-Solomon codes, algebraic coding complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.15
On the Number of Ordinary Lines Determined by Sets in Complex Space

Authors: Abdul Basit, Zeev Dvir, Shubhangi Saraf, and Charles Wolf

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Kelly's theorem states that a set of n points affinely spanning C^3 must determine at least one ordinary complex line (a line passing through exactly two of the points). Our main theorem shows that such sets determine at least 3n/2 ordinary lines, unless the configuration has n-1 points in a plane and one point outside the plane (in which case there are at least n-1 ordinary lines). In addition, when at most n/2 points are contained in any plane, we prove a theorem giving stronger bounds that take advantage of the existence of lines with four and more points (in the spirit of Melchior's and Hirzebruch's inequalities). Furthermore, when the points span four or more dimensions, with at most n/2 points contained in any three dimensional affine subspace, we show that there must be a quadratic number of ordinary lines.
Cite as

Abdul Basit, Zeev Dvir, Shubhangi Saraf, and Charles Wolf. On the Number of Ordinary Lines Determined by Sets in Complex Space. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{basit_et_al:LIPIcs.SoCG.2017.15,
  author =	{Basit, Abdul and Dvir, Zeev and Saraf, Shubhangi and Wolf, Charles},
  title =	{{On the Number of Ordinary Lines Determined by Sets in Complex Space}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.15},
  URN =		{urn:nbn:de:0030-drops-71883},
  doi =		{10.4230/LIPIcs.SoCG.2017.15},
  annote =	{Keywords: Incidences, Combinatorial Geometry, Designs, Polynomial Method}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.34
Arithmetic Circuits with Locally Low Algebraic Rank

Authors: Mrinal Kumar and Shubhangi Saraf

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
In recent years there has been a flurry of activity proving lower bounds for homogeneous depth-4 arithmetic circuits, which has brought us very close to statements that are known to imply VP != VNP. It is a big question to go beyond homogeneity, and in this paper we make progress towards this by considering depth-4 circuits of low algebraic rank, which are a natural extension of homogeneous depth-4 arithmetic circuits. A depth-4 circuit is a representation of an N-variate, degree n polynomial P as P = sum_{i=1}^T Q_{i1} * Q_{i2} * ... * Q_{it} where the Q_{ij} are given by their monomial expansion. Homogeneity adds the constraint that for every i in [T], sum_{j} degree(Q_{ij}) = n. We study an extension where, for every i in [T], the algebraic rank of the set of polynomials {Q_{i1}, Q_{i2}, ... ,Q_{it}} is at most some parameter k. We call this the class of spnew circuits. Already for k=n, these circuits are a strong generalization of the class of homogeneous depth-4 circuits, where in particular t<=n (and hence k<=n). We study lower bounds and polynomial identity tests for such circuits and prove the following results. 1. Lower bounds: We give an explicit family of polynomials {P_n} of degree n in N = n^{O(1)} variables in VNP, such that any spnewn circuit computing P_n has size at least exp{(Omega(sqrt(n)*log(N)))}. This strengthens and unifies two lines of work: it generalizes the recent exponential lower bounds for homogeneous depth-4 circuits [KLSS14, KS-full] as well as the Jacobian based lower bounds of Agrawal et al. which worked for spnew circuits in the restricted setting where T * k <= n. 2. Hitting sets: Let spnewbounded be the class of spnew circuits with bottom fan-in at most d. We show that if d and k are at most poly(log(N)), then there is an explicit hitting set for spnewbounded circuits of size quasipolynomial in N and the size of the circuit. This strengthens a result of Forbes which showed such quasipolynomial sized hitting sets in the setting where d and t are at most poly(log(N)). A key technical ingredient of the proofs is a result which states that over any field of characteristic zero (or sufficiently large characteristic), upto a translation, every polynomial in a set of algebraically dependent polynomials can be written as a function of the polynomials in the transcendence basis. We believe this may be of independent interest. We combine this with shifted partial derivative based methods to obtain our final results.
Cite as

Mrinal Kumar and Shubhangi Saraf. Arithmetic Circuits with Locally Low Algebraic Rank. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 34:1-34:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CCC.2016.34,
  author =	{Kumar, Mrinal and Saraf, Shubhangi},
  title =	{{Arithmetic Circuits with Locally Low Algebraic Rank}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{34:1--34:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.34},
  URN =		{urn:nbn:de:0030-drops-58288},
  doi =		{10.4230/LIPIcs.CCC.2016.34},
  annote =	{Keywords: algebraic independence, arithmetic circuits, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.35
Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing

Authors: Mrinal Kumar and Shubhangi Saraf

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form P = sum_{i=1}^T prod_{j=1}^d Q_{ij} such that each Q_{ij} is an arbitrary polynomial that depends on at most s variables. We prove the following results. 1. Over fields of characteristic zero, for every constant mu such that 0<=mu<=1, we give an explicit family of polynomials {P_{N}}, where P_{N} is of degree n in N = n^{O(1)} variables, such that any representation of the above type for P_{N} with s = N^{mu} requires Td >= n^{Omega(sqrt(n))}. This strengthens a recent result of Kayal and Saha [Kayal/Saha, ECCC 2014] which showed similar lower bounds for the model of sums of products of linear forms in few variables. It is known that any asymptotic improvement in the exponent of the lower bounds (even for s=sqrt(n)) would separate VP and VNP [Kayal/Saha, ECCC 2014]. 2. We obtain a deterministic subexponential time blackbox polynomial identity testing (PIT) algorithm for circuits computed by the above model when T and the individual degree of each variable in P are at most log^{O(1)}(N) and s<=N^{mu} for any constant mu<1/2. We get quasipolynomial running time when s<log^{O(1)}(N). The PIT algorithm is obtained by combining our lower bounds with the hardness-randomness tradeoffs developed in [Dvir/Shpilka/Yehudayoff, SIAM J. Comp. 2009; Kabanets/Impagliazzo, Comp. Compl. 2004]. To the best of our knowledge, this is the first nontrivial PIT algorithm for this model (even for the case s=2), and the first nontrivial PIT algorithm obtained from lower bounds for small depth circuits.
Cite as

Mrinal Kumar and Shubhangi Saraf. Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 35:1-35:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CCC.2016.35,
  author =	{Kumar, Mrinal and Saraf, Shubhangi},
  title =	{{Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{35:1--35:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.35},
  URN =		{urn:nbn:de:0030-drops-58270},
  doi =		{10.4230/LIPIcs.CCC.2016.35},
  annote =	{Keywords: arithmetic circuits, lower bounds, polynomial identity testing, hardness vs randomness}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact